package leetcode_hot100;

import java.util.*;


class ListNode {
    int val;
    ListNode next;

    ListNode(){}
    ListNode(int x) {
        val = x;
        next = null;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}


class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}



public class Demo1 {

    //33. 搜索旋转排序数组
    public int search(int[] nums, int target) {
        // 1.先寻找旋转后右区间中最左边的端点
        int n = nums.length;
        int left = 0, right = n - 1, mid;
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] > nums[n - 1]) left = mid + 1;
            else right = mid;
        }

        if(nums[left] == target) return left;
        // 2. 判断 target 在左右哪个区间
        int index = left;
        left = 0; right = n - 1;
        if(nums[n - 1] >= target) {
            left = index;
        } else if(nums[left] > nums[right] && target > nums[n - 1]){
            right = index - 1;
        }

        // 3. 进行2分查找
        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) right = mid - 1;
            else left = mid + 1;
        }
        return -1;
    }



    //20. 有效的括号
    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();

        char[] arr = s.toCharArray();
        for(int i = 0; i < arr.length; i++) {
            char ch = arr[i];
            if(ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else {
                if(stack.isEmpty()) return false;
                char top = stack.peek();
                if(top == '{' && ch == '}' || top == '[' && ch == ']' || top == '(' && ch == ')') stack.pop();
                else return false;
            }
        }
        return stack.isEmpty();
    }


    //141. 环形链表
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode fast = head.next, slow = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast) break;
        }
        return slow == fast;
    }


    //236. 二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == p || root == q || root == null) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null) return root;

        if(left != null) return left;
        return right;
    }


    //199. 二叉树的右视图
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            int sz = q.size();
            while(sz-- > 0) {
                TreeNode f = q.poll();
                if(sz == 0) ret.add(f.val);
                if(f.left != null) q.offer(f.left);
                if(f.right != null) q.offer(f.right);

            }
        }

        return ret;
    }



    //138. 随机链表的复制
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Map<Node, Node> hash = new HashMap<>();

        Node cur = head;
        while(cur != null) {
            hash.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while(cur != null) {
            hash.get(cur).next = hash.get(cur.next);
            hash.get(cur).random = hash.get(cur.random);
            cur = cur.next;
        }
        return hash.get(head);
    }



    //56. 合并区间
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
        if(intervals.length == 1) return intervals;
        int n = intervals.length;

        List<int[]> list = new ArrayList<>();
        for(int i = 0; i < n; ) {
            int start = intervals[i][0], end = intervals[i][1];
            while(i < n && end >= intervals[i][0]) {
                end = Math.max(end, intervals[i][1]);
                i++;
            }
            list.add(new int[]{start, end});
        }

        int[][] ret = new int[list.size()][2];
        for(int i = 0; i < ret.length; i++) ret[i] = list.get(i);
        return ret;
    }





    //124. 二叉树中的最大路径和
    int ret = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ret;
    }

    public int dfs(TreeNode root) {
        if(root == null) return 0;

        int left = dfs(root.left);
        int right = dfs(root.right);

        // 若子树的结点路径和 小于 0，则不加入路径
        left = Math.max(left, 0);
        right = Math.max(right, 0);

        int sum = root.val + left + right;
        ret = Math.max(ret, sum);

        // 返回给父节点的路径只能由 当前根结点和其左右子树任一路径构成
        return root.val + Math.max(left ,right);
    }




    //41. 缺失的第一个正数
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        int[] hash = new int[n + 1];

        for(int x : nums) {
            if(x > 0 && x <= n) {
                hash[x]++;
            }
        }

        for(int i = 1; i <= n; i++) {
            if(hash[i] == 0) return i;
        }
        return n + 1;
    }



    //39. 组合总和
    List<List<Integer>> ret2;
    List<Integer> path;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret2 = new ArrayList<>();
        path = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, 0);
        return ret2;
    }

    public void dfs(int[] nums, int target, int pos) {
        if(target == 0) {
            ret2.add(new ArrayList<>(path));
            return;
        }

        for(int i = pos; i < nums.length; i++) {
            if(target - nums[i] < 0) break;

            path.add(nums[i]);
            dfs(nums, target - nums[i], i);
            path.remove(path.size() - 1);
        }
    }




    //560. 和为 K 的子数组
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0, 1);

        int sum = 0, ret = 0;
        for(int x : nums) {
            sum += x;
            if(hash.containsKey(sum - k)) ret += hash.get(sum - k);
            hash.put(sum, hash.getOrDefault(sum, 0) + 1);
        }

        return ret;
    }



    //226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null || (root.left == null && root.right == null)) return root;

        TreeNode leftTree = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(leftTree);
        return root;
    }



    //234. 回文链表
    public boolean isPalindrome(ListNode head) {
        if(head.next == null) return true;
        // 1. 寻找链表的中间点
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. 反转后半部分的链表
        ListNode newHead = slow;
        slow = slow.next;
        while(slow != null) {
            ListNode next = slow.next;
            slow.next = newHead;
            newHead = slow;
            slow = next;
        }
        // 3. 从左右两边的链表依次进行遍历，判断是否为回文串
        while(head.val == newHead.val) {
            if(head == newHead || head.next == newHead) return true;
            head = head.next;
            newHead = newHead.next;
        }
        return false;
    }



    //148. 排序链表
    public ListNode sortList(ListNode head) {
        return mergeSort(head, null);
    }

    public ListNode mergeSort(ListNode head, ListNode tail) {
        if(head == null ) return null;
        if(head == tail) {
            head.next = null;
            return head;
        }

        ListNode fast = head, slow = head;  // 寻找该排序区间链表的中点
        while(fast != tail && fast.next != tail) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode list1 = mergeSort(slow.next, tail);     // 必须将此步骤放在前面，因为先得到cur1的话，slow.next 会被置空
        ListNode list2 = mergeSort(head, slow);

        return mergeList(list1, list2);
    }
    public ListNode mergeList(ListNode cur1, ListNode cur2) {
        ListNode tmpHead = new ListNode();
        ListNode rear = tmpHead;
        while(cur1 != null && cur2 != null) {
            if(cur1.val <= cur2.val) {
                rear.next = cur1;
                cur1 = cur1.next;
            } else {
                rear.next = cur2;
                cur2 = cur2.next;
            }
            rear = rear.next;
        }

        if(cur1 != null) rear.next = cur1;
        if(cur2 != null) rear.next = cur2;
        return tmpHead.next;
    }



    //994. 腐烂的橘子
    int[] dx = new int[]{1,-1,0,0};
    int[] dy = new int[]{0,0,1,-1};

    public int orangesRotting(int[][] grid) {
        int count = 0, row = grid.length, col = grid[0].length;      // count记录新鲜橘子的个数
        Queue<int[]> q = new LinkedList<>();    // 存放每轮的烂橘子

        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 1) count++;
                else if(grid[i][j] == 2) q.offer(new int[]{i, j});
            }
        }

        int time = 0;
        while(!q.isEmpty()) {
            int sz = q.size();
            while(sz-- > 0) {
                int[] front = q.poll();
                int i = front[0], j = front[1];
                for(int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if(x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        count--;
                        q.offer(new int[]{x, y});
                    }
                }
            }
            if(!q.isEmpty()) time++;
        }

        if(count > 0) return -1;
        return time;
    }




    //347. 前 K 个高频元素
    public int[] topKFrequent(int[] nums, int k) {
        // 统计各元素出现的次数
        Map<Integer, Integer> hash = new HashMap<>();
        for(int x : nums) {
            hash.put(x, hash.getOrDefault(x, 0) + 1);
        }

        // 将哈希表的元素放到 数组中
        List<int[]> list = new ArrayList<>();
        for(Integer key : hash.keySet()) {
            int[] arr = new int[]{key, hash.get(key)};
            list.add(arr);
        }

        // 快速选择
        quickSelect(list, 0, list.size() - 1, k);
        int[] ret = new int[k];
        for(int i = list.size() - 1; k > 0; k--, i--) {
            ret[k - 1] = list.get(i)[0];
        }
        return ret;
    }
    public void quickSelect(List<int[]> list, int left, int right, int k) {
        if(left >= right) return;

        // 随机选择一个频率
        int[] random = list.get(left + new Random().nextInt(right - left));
        int frequency = random[1];
        int l = left - 1, r = right + 1, cur = left;
        while(cur < r) {
            int[] arr = list.get(cur);
            if(arr[1] == frequency) cur++;
            else if(arr[1] < frequency) Collections.swap(list, ++l, cur++);
            else Collections.swap(list, --r, cur);
        }

        // [left, l]: 频率小于 frequency,  [l + 1, cur - 1]:频率等于 frequency,  [r, right]:频率大于 frequency
        int a = cur - l - 1, b = right - r + 1;
        if(b >= k) quickSelect(list, r, right, k);
        else if(a + b >= k) return;
        else quickSelect(list, left, l, k - a - b);
    }


    //114. 二叉树展开为链表
    TreeNode prev;
    public void flatten(TreeNode root) {
        // 先序遍历
        if(root == null) return;

        if(prev != null) prev.right = root;
        prev = root;

        TreeNode rightTree = root.right;        // 保存右子树结点信息，防止递归遍历时 root.right指向被改变
        flatten(root.left);
        root.left = null;                       // 处理完左子树后，将左子树指向置空
        flatten(rightTree);
    }




    //118. 杨辉三角
    public List<List<Integer>> generate(int numRows) {

        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    list.add(1);
                } else {
                    List<Integer> tmp = ret.get(i - 1);
                    list.add(tmp.get(j) + tmp.get(j - 1));
                }
            }
            ret.add(list);
        }
        return ret;
    }



    //49. 字母异位词分组
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();

        for(String str : strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);

            if(!hash.containsKey(key)) {
                hash.put(key, new ArrayList<>());
            }
            hash.get(key).add(str);
        }

        return new ArrayList<>(hash.values());
    }



    // 207. 课程表
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 拓扑排序：验证是否有环，bi -> ai
        Map<Integer, List<Integer>> hash = new HashMap<>();     // 记录各课程的出度
        int[] count = new int[numCourses];                      // 记录各课程的入度
        for(int[] arr : prerequisites) {
            int a = arr[0], b = arr[1];
            if(!hash.containsKey(b)) hash.put(b, new ArrayList<>());
            hash.get(b).add(a);
            count[a]++;
        }

        Queue<Integer> q = new LinkedList<>();          // 记录入度为0的课程
        for(int i = 0; i < numCourses; i++) {
            if(count[i] == 0) q.offer(i);
        }

        // 尝试拓扑排序
        int ret = numCourses;
        while(!q.isEmpty()) {
            int course = q.poll();
            ret--;
            List<Integer> list = hash.get(course);

            if(list == null) continue;
            for(Integer x : list) {
                if(--count[x] == 0) q.offer(x);
            }
        }
        return ret == 0;
    }



    //34. 在排序数组中查找元素的第一个和最后一个位置
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        int left = 0, right = nums.length - 1, mid, n = nums.length;
        if(n == 0) return ret;
        // 寻找左端点
        while(left < right) {
            mid = left + (right - left) / 2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        if(nums[left] == target) ret[0] = left;

        // 寻找右端点
        for(left = 0, right = nums.length - 1; left < right; ) {
            mid = left + (right - left + 1) / 2;
            if(nums[mid] > target) right = mid - 1;
            else left = mid;
        }
        if(nums[left] == target) ret[1] = left;
        return ret;
    }




    //94. 二叉树的中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;

        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()) {
            if(root != null) {
                stack.push(root);
                root = root.left;
            } else {
                TreeNode top = stack.pop();
                ret.add(top.val);
                root = top.right;
            }
        }
        return ret;
    }



    //79. 单词搜索
    int row, col;
    boolean[][] vis;
//    int[] dx = new int[]{0,0,1,-1};
//    int[] dy = new int[]{1,-1,0,0};

    public boolean exist(char[][] board, String _word) {
        row = board.length;
        col = board[0].length;
        vis = new boolean[row][col];
        char[] word = _word.toCharArray();

        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++) {
                if(board[i][j] == word[0]) {
                    if(dfs(board, i, j, word, 0)) return true;
                }
            }
        return false;
    }
    private boolean dfs(char[][] board, int i, int j, char[] word, int pos) {
        vis[i][j] = true;
        pos++;
        if(pos == word.length) return true;

        for(int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < row && y >= 0 && y < col && !vis[x][y] && board[x][y] == word[pos]) {
                if(dfs(board, x, y, word, pos)) return true;
            }
        }
        vis[i][j] = false;
        return false;
    }



    //240. 搜索二维矩阵 II
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int i = 0, j = n - 1;
        while(i < m && j >= 0) {
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] > target) j--;
            else i++;
        }
        return false;
    }



    //238. 除自身以外数组的乘积
    public int[] productExceptSelf(int[] nums) {
        int[] f = new int[nums.length];
        int[] g = new int[nums.length];
        f[0] = 1; g[nums.length - 1] = 1;
        // 计数前 i 项元素的积
        for(int i = 1; i < nums.length; i++)
            f[i] = f[i-1] * nums[i-1];
        // 计算后 i 项元素的积
        for(int i = nums.length - 2; i >= 0; i--)
            g[i] = g[i+1] * nums[i+1];
        // 利用前缀积和后缀积 计算结果
        int[] ret = new int[nums.length];
        for(int i = 0; i < nums.length; i++) ret[i] = f[i] * g[i];
        return ret;
    }



    //105. 从前序与中序遍历序列构造二叉树
    int pos = 0;
    Map<Integer, Integer> hash = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0; i < inorder.length; i++) hash.put(inorder[i], i);
        return constructTree(preorder, inorder, 0, inorder.length - 1);
    }
    private TreeNode constructTree(int[] preorder, int[] inorder, int left, int right) {
        if(left > right) return null;
        TreeNode root = new TreeNode(preorder[pos++]);
        // 寻找当前树的根结点在中序遍历的下标
        int index = hash.get(root.val);
        root.left = constructTree(preorder, inorder, left, index - 1);
        root.right = constructTree(preorder, inorder, index + 1, right);
        return root;
    }




    //55. 跳跃游戏
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if(n == 1) return true;
        int left = 0, right = 0, nextRight = 0;

        while(left <= right) {
            for(; left <= right; left++) {
                if(left + nums[left] >= n - 1) return true;
                nextRight = Math.max(nextRight, left + nums[left]);
            }
            left = right + 1;
            right = nextRight;
        }
        return false;
    }



    //75. 颜色分类
    public void sortColors(int[] nums) {
        // left下标代表红色的最后一个位置，right下标代表蓝色的第一个位置
        // 红色[0,left]   白色[left+1,right-1]   蓝色[right,len-1]
        int left = -1, right = nums.length, i = 0;
        while(i < right) {
            if(nums[i] == 0) swap(nums,++left,i++);
            else if(nums[i] == 1) i++;
            else swap(nums,--right,i);
        }
    }
    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }




    //51. N 皇后
    List<List<String>> ret3;
    List<String> path3;
    StringBuffer _tmp;
    boolean[] col3;      // 记录该列是否有皇后
    boolean[] a;        // 记录正对角线是否有皇后
    boolean[] b;        // 记录反对角线是否有皇后

    public List<List<String>> solveNQueens(int n) {
        ret3 = new ArrayList<>();
        col3 = new boolean[n];
        path = new ArrayList<>();
        a = new boolean[n * 2];
        b = new boolean[n * 2];
        _tmp = new StringBuffer();
        for(int i = 0; i < n; i++) _tmp.append('.');

        dfs(n, 0);
        return ret3;
    }

    private void dfs(int n, int pos) {  //pos 记录当前行数
        if(path3.size() == n) {
            ret3.add(new ArrayList<>(path3));
            return;
        }

        // i 表示当前所处的列
        for(int i = 0; i < n; i++) {
            if(col3[i] == false && !a[i - pos + n] && !b[i + pos]) {
                StringBuffer tmp = new StringBuffer(_tmp);
                tmp.setCharAt(i, 'Q');
                path3.add(tmp.toString());
                col3[i] = true; a[i - pos + n] = true; b[i + pos] = true;
                dfs(n, pos + 1);
                path3.remove(path.size() - 1);      // 恢复现场
                col3[i] = false; a[i - pos + n] = false; b[i + pos] = false;
            }
        }
    }




    //78. 子集
    List<List<Integer>> ret4;
    List<Integer> path4;

    public List<List<Integer>> subsets(int[] nums) {
        ret4 = new ArrayList<>();
        path4 = new ArrayList<>();

        dfs(nums, 0);
        return ret4;
    }

    private void dfs(int[] nums, int pos) {
        ret4.add(new ArrayList<>(path4));
        if(pos == nums.length) return;

        for(int i = pos; i < nums.length; i++) {
            path4.add(nums[i]);
            dfs(nums, i + 1);
            path4.remove(path4.size() - 1);
        }
    }




    //19. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode fast = head, slow = head, prev = newHead;

        while(n-- > 0)  fast = fast.next;
        while(fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }

        prev.next = slow.next;
        return newHead.next;
    }



    //169. 多数元素
    public int majorityElement(int[] nums) {
        int ret = 0, count = 0;
        for(int x : nums) {
            if(count == 0) {
                ret = x;
                count++;
            } else {
                if(x == ret) count++;
                else count--;
            }
        }

        return ret;
    }




    //230. 二叉搜索树中第K小的元素
    int count, ret6 = -1;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inOrder(root);
        return ret6;
    }

    private void inOrder(TreeNode root) {
        if(root == null) return;

        if(count > 0) inOrder(root.left);
        if(--count == 0) {
            ret6 = root.val;
        }
        if(count > 0) inOrder(root.right);
    }



    //46. 全排列
    List<List<Integer>> ret7;
    List<Integer> path7;
    boolean[] vis7;

    public List<List<Integer>> permute(int[] nums) {
        ret7 = new ArrayList<>();
        path7 = new ArrayList<>();
        vis7 = new boolean[nums.length];

        dfs(nums);
        return ret7;
    }

    private void dfs(int[] nums) {
        if(path7.size() == nums.length) {
            ret7.add(new ArrayList<>(path7));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!vis7[i]) {
                vis7[i] = true;
                path7.add(nums[i]);
                dfs(nums);
                vis7[i] = false;
                path7.remove(path7.size() - 1);
            }
        }
    }



    //131. 分割回文串
    List<List<String>> ret8;
    List<String> path8;

    public List<List<String>> partition(String s) {
        // dp[i][j]: 字符串s i ~ j 区间的子串是否为回文子串
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n - 1; i >= 0; i--)
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }

        ret8 = new ArrayList<>();
        path8 = new ArrayList<>();
        dfs(s, 0, dp);
        return ret8;
    }

    public void dfs(String s, int pos, boolean[][] check) {
        if(pos == s.length()) {
            ret8.add(new ArrayList<>(path8));
            return;
        }

        for(int i = pos; i < s.length(); i++) {
            if(check[pos][i]) {
                path8.add(s.substring(pos, i + 1));
                dfs(s, i + 1, check);
                path8.remove(path8.size() - 1);
            }
        }
    }




    //22. 括号生成
    List<String> ret9;
    StringBuilder path9;

    public List<String> generateParenthesis(int n) {
        ret9 = new ArrayList<>();
        path9 = new StringBuilder();
        dfs(n, 0, 0);
        return ret9;
    }

    public void dfs(int n, int left, int right) {
        if(path9.length() == 2 * n) {
            ret9.add(path9.toString());
            return;
        }

        // 添加右括号
        if(left > right) {
            path9.append(')');
            dfs(n, left, right + 1);
            path9.deleteCharAt(path9.length() - 1);
        }
        if(left < n) {
            path9.append('(');
            dfs(n, left + 1, right);
            path9.deleteCharAt(path9.length() - 1);
        }
    }



    //155. 最小栈
    class MinStack {
        Deque<Integer> t1;
        Deque<Integer> t2;


        public MinStack() {
            t1 = new LinkedList<>();
            t2 = new LinkedList<>();
        }

        public void push(int val) {
            t1.push(val);
            if(t2.isEmpty() || val <= t2.peek()) t2.push(val);
        }

        public void pop() {
            int val = t1.pop();
            if(val == t2.peek()) t2.pop();
        }

        public int top() {
            return t1.peek();
        }

        public int getMin() {
            return t2.peek();
        }
    }


}
